package algorithmic_data_structure.二叉树递归套路;

import java.util.LinkedList;

public class 是否完全二叉树 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public boolean isCBT(TreeNode root){
        if (root == null){
            return true;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean flag = false;
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            TreeNode left = node.left;
            TreeNode right = node.right;
            if (flag){//表示已经遇到过左右节点不全的节点了
                if (left != null || right != null){
                    return false;
                }
            }
            if (left == null && right != null){
                return false;
            }
            if (left != null){
                queue.offer(left);
            }
            if (right != null){
                queue.offer(right);
            }else {
                //小心思 ： 通过右节点是否为空就可以判断是否可以开始判断叶子节点了
                flag = true;
            }

        }
        return true;
    }
}
